#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// 创建
int e[N], ne[N], h, id;
int mp[N]; // mp[i] 表示 i 这个数存储的位置

// 遍历链表
void print()
{
    for(int i = ne[h]; i; i = ne[i])
    {
        cout << e[i] << " ";
    }
    cout << endl << endl;
}

// 头插
void push_front(int x)
{
    id++;
    e[id] = x;
    mp[x] = id; // 标记 x 存储的位置

    // 先让新结点指向头结点的下一个位置
    // 然后让头结点指向新来的结点
    ne[id] = ne[h];
    ne[h] = id;
}

// 按值查找
int find(int x)
{
    // // 解法一：遍历链表
    // for(int i = ne[h]; i; i = ne[i])
    // {
    //     if(e[i] == x) return i;
    // }
    // return 0;

    // 解法二：用 mp 数组优化
    return mp[x];
}

// 在任意位置 p 之后，插入一个新的元素 x
void insert(int p, int x)
{
    id++;
    e[id] = x;
    mp[x] = id;

    ne[id] = ne[p];
    ne[p] = id;
}

// 删除任意位置 p 后面的元素
void erase(int p)
{
    if(ne[p]) // 当 p 不是最后一个元素的时候
    {
        mp[e[ne[p]]] = 0; // 把标记清空

        ne[p] = ne[ne[p]];
    }
}

int main()
{
    for(int i = 1; i <= 5; i++)
    {
        push_front(i);
        print();
    }

    //cout << find(1) << endl;
    //cout << find(5) << endl;
    //cout << find(6) << endl;

    // insert(1, 10);
    // print();
    // insert(2, 100);
    // print();

    erase(2);
    print();
    erase(4);
    print();

    return 0;
}